/*
 * @Description: 
 * @Version: 1.0
 * @Autor: ziwei
 * @Date: 2021-04-13 09:43:31
 * @LastEditors: ziwei
 * @LastEditTime: 2021-04-15 09:39:38
 */
//20210411 手写二叉搜索树 难度还可以听懂了
//要求会写的
class Node{
    //创建节点要告诉我 元素和爸爸
    constructor(element,parent){
        this.element = element;
        this.parent = parent;//标记父节点
        this.left = null;//左边
        this.right = null;
    }
}

class Tree{
    constructor(){
        this.root = null;//默认空树
    }

    add(element){
        if(this.root == null){
            return this.root = new Node(element);
        }

        //可以用递归 用循环就可以了
        let currentNode = this.root;//更新当前更节点
        let parent;
        let compare;
        while (currentNode) {
            compare = currentNode.element < element;
            parent = currentNode;
            if (compare){
                currentNode = currentNode.right
            }else{
                currentNode = currentNode.left;
            }
        }

        let newNode = new Node(element, parent);
        if (compare){
            parent.right = newNode
        }else{
            parent.left = newNode;
        }

        // while (currentNode) {//更新
        //     if(currentNode.element<element){//10 19
        //         //
        //     }
        // }
        //如何实现 左边和右边分开存放
        // if(currentNode.element < element){//比根节点大
        //     currentNode.right = new Node(element,currentNode);
        // }else{
        //     currentNode.left = new Node(element,currentNode);
        // }
    }
}

let tree = new Tree();
[10,8,19,6,15,22,20].forEach(i=>{
    tree.add(i)
})
console.dir(tree,{depth:100})

//关键代码在24-42 
// 1:一个类Node 上有自己 左右和爸爸4个属性
//用while循环 找出我应该被插入到哪个父亲节点下 分左边和右边: 找到父亲和 判断左边还是右边的标志
//找到后进行插入

// 后序：左中右